/**
 * Created by L.jp
 * Description:对于长度为n的一个字符串A（仅包含数字，大小写英文字母），
 * 请设计一个高效算法，计算其中最长回文子串的长度。
 *
 *
 * 数据范围：1≤n≤1000
 * 要求：空间复杂度 O(1)，时间复杂度 O(n^2)
 * 2
 *  )
 * 进阶:  空间复杂度 O(n)，时间复杂度 O(n)
 * User: 86189
 * Date: 2022-05-28
 * Time: 10:16
 * @author 86189
 */
public class Solution {
    public static int getLongestPalindrome (String A) {
        char[] s=A.toCharArray();
        int n=A.length();
        //方法一：动态规划算法
        //dp[i][j]表示字符串从i到j位置是否为回文字符串
        boolean[][] dp = new boolean[n][n];
        //初始化，从i到i，单个字符也是回文字符串
        for (int i = 0; i < n; i++) {
            dp[i][i]=true;
        }
        //回文子串长度最长是1
        int maxLen=1;
        /*如果s[i]==s[j]，而且dp[i+1][j-1]是回文字符串，那么dp[i][j]也是回文字符串
        * 所以我们的i需要从后往前循环，j需要从前往后遍历*/
        //只需要构造一半的数组，对于i>j的地方是不存在合法字符串的
        for (int i=n-1; i>=0; i--) {
            for (int j=i; j<n; j++) {
                if (s[i] == s[j]) {
                    //i,j之间大于等于2个字符
                    if (i+1 <= j-1){
                        if (dp[i+1][j-1]) {
                            dp[i][j] = true;
                        }
                    }else{
                        //j-i<2,最多两个字符，并且s[i]和s[j]相等，那么必定是回文字符串
                        dp[i][j]=true;
                    }
                }
                if (dp[i][j]) {
                    int len = j - i + 1;
                    if (len>maxLen) {
                        maxLen = len;
                    }
                }
            }
        }
        return maxLen;
    }
    
    public static void main ( String[] args ) {
        String str="ababc";
        System.out.println( getLongestPalindrome( str ) );
    }
}
